Three dimensional volume visualization has been used in various applications such as in medical diagnoses, weather forecasting, molecular design, etc. There are two types of fundamental techniques which can be used for volume visualization: volume rendering and surface rendering. A few popular surface rendering techniques have been developed and extensively used in many interactive applications.
With either of these techniques, the fundamental data formation is denoted as volume data depicting a 3-dimensional space scalar field, d=d(x, y, z), which represents a set of values for a certain physical characteristic of a three dimensional object. The volume data is partitioned into N.times.N.times.N identical cubes, called cells, having 6 faces and 8 voxels or vertices, each voxel being associated with the physical characteristic, e.g. density denoted as d.sub.i,j,k, of the 3-dimensional object. There are currently a number of well-known surface rendering methods for displaying surface structure of a three dimensional object from a set of volume data as defined above. For instance, Gordon and Udupa have developed a surface tracking algorithm as fully detailed in the publication, D. Gordon and J. K. Udupa, "Fast Surface Tracking in Three-Dimensional Binary Images", Computer Vision, Graphics, and Image Processing, 45, 2, pp. 196-214, February 1989, which was successfully used in TURNKEY medical systems.
In this algorithm, Gordon and Udupa define two types of cells subject to the sign of the difference of the density value, d.sub.i,j,k, of an object and a threshold t. If d.sub.i,j,k -t&lt;0 then c.sub.i,j,k is classified as a 0-cell; otherwise it is deemed a 1-cell. The object is deemed to contain all 1-cells and the background is deemed to contain all 0-cells. All boundary face between 1-cells and 0-cells is defined to be the object surface. The boundary face is called the B-face. Gordon and Udupa developed an algorithm called surface tracking to track and detect all such B-faces. Before the algorithm is invoked, a cell called seed which has at least one B-face is given.
The surface tracking algorithm has two main disadvantages. First, the object to be visualized must be connected and the seed must be provided. Providing the seed sometimes is not as easy as one might imagine. To illustrate this point, FIG. 1 shows an example of a 2-dimensional object which has three possible densities at individual voxels, i.e. 0, d or d'(&gt;d&gt;0). Given a threshold 0&lt;t.sub.1 &lt;d, and using the above definition, there are 27 1-cells which form a connected object. Assuming that a seed, say, c.sub.1,1 is given, the algorithm can track all the B-faces (in a 2-dimensional case, they are actually edges ), i.e. the outlay contour of the object. However, it is quite often that this resultant contour is not the one the user wishes to see. He might adjust the threshold to d'&gt;t.sub.2 &gt;d. This results in a new object which consists of two parts. The original seed c.sub.1,1 no longer belongs to the object and is useless for the surface tracking purpose. Two new seeds must be provided so that the algorithm can detect new boundaries for each individual part. This is obviously computationally intensive. In general, the user should be allowed to change the threshold interactively with the system to generate corresponding object images. In order to do so, there should be some mechanism to provide all seeds which are dynamically adjustable with different user-specified thresholds. Without the special mechanism, all cells must be check resulting in time complexity of O(N.sup.3).
The second disadvantage is that the algorithm generates a number of B-faces to patch the object surface. Compared with other patching techniques such as the triangulation methods known to those skilled in the art, the resultant images can have greater distortions and poorer quality.
One popular triangulation patching algorithm, known as Marching Cubes, developed by Lorensen and Cline and described in US. Pat. No. 4,719,585 and U.S. Pat. No. 4,729,098, overcomes some of the shortcomings of the Gordon and Udupa algorithm. The Marching Cube algorithm first obtains all borders of the object on each cross section and then patches them using triangles. In order to detect all cross section parts, three types of cells are defined. Given a threshold t, a cell is defined as a 1-cell if each of its eight vertices has a density greater than t, and a 0-cell if each of its eight vertices has a density less than t. A cross-sectional-cell, or an S-cell is a cell which contains some voxels with densities greater than the threshold t, and some voxels with densities less than the threshold t.
Hence, with the Marching Cube algorithm, the B-faces as defined and utilized in the Surface Tracking Algorithm no longer exist because the new definition of a 1-cell will never neighbor a 0-cell. Only S-cells contain object iso-surface. In order to triangulate each of the S-cells, Lorenson and Cline have summarized 14 rules of how to patch the surface part of an S-cell. Applying these rules on each S-cell, the object image can be nicely generated. The algorithm is called the Marching Cubes because it must march every cell once. Although the algorithm has been generally successful, it has been reported that the 14 rules contain some ambiguity which would result in images with artificial holes. Suggestions to remove the ambiguity and the artificial holes have been discussed in J. Wiuheims and A. Van Gelder, "Octree for Faster Isosurface Generation", Computer Graphics, 24(5), November, 1990, pp.57-61.
As technologies are upgraded and as higher resolution volume data become available in imaging applications, there is a greater need to reduce computational time to access the needed data and to generate the image. For example, in a modern computer tomography (CT) and magnetic resonance imaging, (MRI) with lower radiosity, they can generate volume data with much greater resolution N. While the increased resolution allows for greater accuracy and safety for diagnostic purposes, the size of the data with O(N.sup.3) complexity could severely diminish the performance of the imaging system because the checking of all cells, as required by the Marching Cube algorithm, can take O(N.sup.3) steps.
To combat this problem, researchers created new data structures to improve the speed performance. Although these data structures often occupied greater memory space, they increased the rendering speed. Rendering speed is particularly important in many of the present interactive applications where the it is necessary to generate isosurfaces of different threshold values. Hence, this was seen as a worthwhile tradeoff as memory hardware became cheaper.
One such improved data structure was developed by M. Levoy, who first up ray casting. J. Wilhelms and A. Gelder improved on this data structure by proposing a summarized-information octree (SIO) for surface rendering techniques which is particularly suited for the Marching Cubes algorithm. The SIO builds up a 3-D octree according to the geometrical neighboring relationship between cells and can be used for surface rendering algorithms such as the Marching Cubes to avoid exploring regions of little or no interest within the volume data. The savings in the processing time can be as much as 40%. However, SIO can take up enormous amount of memory space (could be as large as 40M words) in generating a large number of what-is-known-as summarized information pairs. If the dimensions of the 3-dimensional volume data set are not simply the power of two, then a substantial amount of the space could be wasted. An improvement of the SIO called BONO has been proposed in J. Wilhelms and A. Van Gelder, "Octree for Faster Isosurface Generation", Computer Graphics, 24(5), November 1990, pp.57-61.
In light of the shortcomings stated above, and the continual demand for improved speed performance and the efficient utilization of memory space for surface rendering, there is clearly a need to have a data structure and a method and system for using the same which can efficiently use the volume data to significantly improve the speed performance of surface rendering without incurring equally significant increase in the memory requirement, and which would be particularly useful in interactive applications where faster rendering speed is highly desirable.